package com.lhgg.sd;

import java.util.*;

/**
 * @ClassName Sd
 * @Description TODO
 * @Author 黄鹏祥
 * @Date 2020/12/8 21:04
 * @Version 1.0
 **/
public class Sd {

    //    结果矩阵
    private final short[][] RESULT = {
//            简单
//            {0, 5, 0, 0, 0, 2, 0, 0, 0},
//            {0, 0, 0, 0, 1, 0, 3, 2, 0},
//            {8, 0, 0, 0, 4, 0, 1, 0, 0},
//            {0, 2, 6, 0, 5, 3, 0, 1, 0},
//            {9, 4, 3, 0, 6, 1, 5, 7, 0},
//            {0, 0, 8, 0, 9, 7, 6, 4, 3},
//            {0, 0, 9, 0, 7, 0, 2, 8, 1},
//            {2, 7, 1, 6, 0, 8, 4, 9, 5},
//            {4, 8, 5, 0, 0, 9, 7, 3, 6},

//            {5, 0, 7, 1, 6, 0, 0, 0, 0,},
//            {8, 0, 0, 0, 2, 0, 0, 0, 6},
//            {0, 9, 6, 0, 0, 0, 0, 5, 8},
//            {0, 6, 0, 0, 4, 0, 1, 8, 0,},
//            {0, 0, 5, 8, 0, 0, 9, 4, 0,},
//            {0, 0, 8, 5, 0, 0, 0, 0, 0,},
//            {2, 0, 0, 6, 8, 0, 0, 0, 4},
//            {0, 3, 4, 0, 0, 9, 0, 0, 0,},
//            {6, 0, 0, 0, 3, 4, 5, 0, 0,},

//            {0, 6, 0, 0, 5, 0, 7, 0, 0,},
//            {0, 7, 1, 8, 0, 2, 5, 6, 3,},
//            {0, 9, 0, 6, 0, 3, 8, 1, 0,},
//            {0, 0, 0, 0, 0, 9, 6, 0, 1,},
//            {6, 0, 0, 0, 0, 4, 0, 7, 5,},
//            {1, 0, 4, 0, 0, 0, 9, 8, 2,},
//            {0, 1, 6, 9, 0, 7, 0, 5, 0,},
//            {0, 4, 8, 0, 3, 0, 0, 0, 7,},
//            {0, 0, 0, 0, 4, 8, 2, 3, 0,},

//            中等
//            {0, 0, 0, 0, 0, 8, 0, 4, 9,},
//            {4, 9, 8, 6, 1, 0, 5, 0, 0,},
//            {3, 2, 0, 0, 0, 0, 7, 8, 0,},
//            {0, 0, 0, 1, 0, 0, 4, 9, 0,},
//            {7, 0, 0, 0, 5, 0, 3, 0, 0,},
//            {0, 3, 0, 2, 6, 4, 8, 7, 1,},
//            {5, 0, 0, 0, 0, 0, 0, 0, 0,},
//            {1, 0, 0, 5, 8, 6, 0, 0, 0,},
//            {0, 0, 0, 0, 3, 1, 2, 0, 7,},

//            困难
//            {0, 2, 0, 4, 0, 9, 1, 0, 0,},
//            {0, 0, 6, 0, 5, 0, 0, 8, 9,},
//            {0, 7, 0, 0, 8, 3, 0, 2, 4,},
//            {7, 1, 0, 5, 0, 0, 0, 0, 0,},
//            {0, 0, 0, 0, 9, 0, 2, 0, 0,},
//            {0, 0, 0, 0, 4, 0, 0, 0, 7,},
//            {0, 6, 0, 0, 0, 0, 0, 0, 0,},
//            {0, 0, 7, 3, 0, 0, 8, 0, 1,},
//            {3, 4, 0, 0, 0, 5, 0, 6, 0,},

//            专家
//            {2, 0, 0, 0, 0, 8, 0, 0, 7},
//            {6, 0, 0, 0, 7, 0, 0, 0, 4},
//            {0, 0, 0, 9, 5, 0, 0, 0, 0,},
//            {0, 8, 3, 0, 0, 0, 0, 6, 0,},
//            {0, 0, 0, 3, 0, 0, 4, 0, 0,},
//            {0, 0, 5, 0, 2, 0, 0, 0, 8},
//            {5, 7, 0, 0, 0, 4, 0, 0, 0,},
//            {0, 4, 0, 1, 0, 0, 2, 0, 0,},
//            {0, 0, 0, 0, 9, 0, 0, 4, 0,},

//            号称史上最难的
            {8, 0, 0, 0, 0, 0, 0, 0, 0,},
            {0, 0, 3, 6, 0, 0, 0, 0, 0,},
            {0, 7, 0, 0, 9, 0, 2, 0, 0,},
            {0, 5, 0, 0, 0, 7, 0, 0, 0,},
            {0, 0, 0, 0, 4, 5, 7, 0, 0,},
            {0, 0, 0, 1, 0, 0, 0, 3, 0,},
            {0, 0, 1, 0, 0, 0, 0, 6, 8,},
            {0, 8, 5, 0, 0, 0, 0, 1, 0,},
            {0, 9, 0, 0, 0, 0, 4, 0, 0,}

    };

    private final List<Short>[][] ERZ_MAP = new ArrayList[9][9];

    //    快照列表
    private final SnapshotList snapshotList = SnapshotList.getInstance();

    /**
     * 打印每个格子可能出现的数字
     */
    private void printEjzMap() {
        for (int x = 0; x < 9; x++) {
            for (int y = 0; y < 9; y++) {
                if (ERZ_MAP[x][y].size() == 1) {
                    System.out.print(("{" + ERZ_MAP[x][y].iterator().next() + "} "));
                } else {
                    System.out.print("[" + ERZ_MAP[x][y].size() + "] ");
                }
            }
            System.out.println("\n");
        }
    }

    /**
     * 初始化每个格子的可能性
     */
    private void initMap() {
        for (int x = 0; x < 9; x++) {
            for (int y = 0; y < 9; y++) {
                final short num = RESULT[x][y];
                if (num > 0) {
                    ERZ_MAP[x][y] = new ArrayList<>(1) {{
                        add(num);
                    }};
                } else {
                    ERZ_MAP[x][y] = new ArrayList<>(9) {{
                        add((short) 1);
                        add((short) 2);
                        add((short) 3);
                        add((short) 4);
                        add((short) 5);
                        add((short) 6);
                        add((short) 7);
                        add((short) 8);
                        add((short) 9);
                    }};
                }
            }
        }
    }

    private void calc() {
//        System.out.println("第一轮，先算出每个格子内可能出现的所有数字。");
        for (short x = 0; x < 9; x++) {
            for (short y = 0; y < 9; y++) {
                calcOne(x, y);
            }
        }
//        System.out.println("第二轮，尝试。");
        Integer currTryCount = null;
        short x = 0;
        while (x < 9) {
            short y = 0;
            while (y < 9) {
//                如果备选数字的多于1个，则需要尝试
                if (ERZ_MAP[x][y].size() > 1) {
                    final boolean tryFlag = this.tryGrid(x, y, currTryCount);
                    if (!tryFlag) {
//                        System.out.println("尝试单元格: " + x + "," + y + "，全部不通过。");
//                        取出上一个快照
                        final Snapshot last = this.snapshotList.getLast();
                        this.snapshotList.removeLast();
//                        还原快照
                        for (short x0 = 0; x0 < 9; x0++) {
                            for (short y0 = 0; y0 < 9; y0++) {
                                ERZ_MAP[x0][y0] = last.getContent()[x0][y0];
                            }
                        }
//                        回到上次创建快照时的单元格
                        x = last.getX();
                        y = last.getY();
                        currTryCount = last.getCurrIndex() + 1;
                        continue;
                    }
                }
                currTryCount = null;
                y++;
            }
            x++;
        }
    }

    /**
     * 尝试
     *
     * @param x
     * @param y
     * @return
     */

    private boolean tryGrid(short x, short y, Integer currTryCount) {
//        待尝试的队列
        final List<Short> list = ERZ_MAP[x][y];
        currTryCount = currTryCount == null ? 1 : currTryCount;
        for (; currTryCount <= list.size(); currTryCount++) {
            final short tryNum = ERZ_MAP[x][y].get(currTryCount - 1);
            final boolean tryFlag = this.validate(x, y, tryNum);
            if (tryFlag) {
//                System.out.println("尝试单元格: " + x + "," + y + "，数字" + tryNum + "，通过。");
//                创建当前状态的快照
//                System.out.println("创建当前状态的快照");
                this.createSnapshot(x, y, currTryCount);
//                填充此单元格
                ERZ_MAP[x][y] = new ArrayList<>() {{
                    add(tryNum);
                }};
                return true;
//            } else {
//                System.out.println("尝试单元格: " + x + "," + y + "，数字" + tryNum + "，不通过。");
            }
        }
        return false;
    }

    /**
     * 验证数字在这个单元格是否合法
     *
     * @param x
     * @param y
     * @param num
     * @return
     */
    private boolean validate(short x, short y, short num) {
//        横向验证
        for (short i = 0; i < 9; i++) {
            if (i == x || ERZ_MAP[i][y].size() > 1) {
                continue;
            }
            if (ERZ_MAP[i][y].get(0) == num) {
                return false;
            }
        }
//        纵向验证
        for (short i = 0; i < 9; i++) {
            if (i == y || ERZ_MAP[x][i].size() > 1) {
                continue;
            }
            if (i != y && ERZ_MAP[x][i].get(0) == num) {
                return false;
            }
        }
//        宫内计算
        for (short i = (short) (x / 3 * 3), i0 = 0; i0 < 3; i++, i0++) {
            for (short j = (short) (y / 3 * 3), j0 = 0; j0 < 3; j++, j0++) {
                if (i == x && j == y || ERZ_MAP[i][j].size() > 1) {
                    continue;
                }
                if (ERZ_MAP[i][j].get(0) == num) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 创建当前状态的快照
     */
    private void createSnapshot(short x, short y, int index) {
        List<Short>[][] snapshot = new ArrayList[9][9];
        for (short x0 = 0; x0 < 9; x0++) {
            for (short y0 = 0; y0 < 9; y0++) {
                snapshot[x0][y0] = ERZ_MAP[x0][y0];
            }
        }
        snapshotList.put(new Snapshot(snapshot, x, y, index));
    }

    private boolean calcOne(short x, short y) {
        final List<Short> arr = ERZ_MAP[x][y];
//                长度为1，说明此格子有明确的数字
        if (arr.size() == 1) {
//                    此格的数字
            final short num = arr.get(0);
//                    横向计算
            for (short i = 0; i < 9; i++) {
                final List<Short> tempArr0 = ERZ_MAP[x][i];
                if (tempArr0.size() > 1) {
                    final List<Short> tempArr1 = new ArrayList<>();
                    Iterator<Short> it = tempArr0.iterator();
                    while (it.hasNext()) {
                        final short num1 = it.next();
                        if (num1 != num) {
                            tempArr1.add(num1);
                        }
                    }
                    if (tempArr1.isEmpty()) {
                        return false;
                    }
                    ERZ_MAP[x][i] = tempArr1;
                    if (tempArr1.size() == 1) {
                        calcOne(x, i);
                    }
                }
            }
//                    纵向计算
            for (short i = 0; i < 9; i++) {
                final List<Short> tempArr0 = ERZ_MAP[i][y];
                if (tempArr0.size() > 1) {
                    final List<Short> tempArr1 = new ArrayList<>();
                    Iterator<Short> it = tempArr0.iterator();
                    while (it.hasNext()) {
                        final short num1 = it.next();
                        if (num1 != num) {
                            tempArr1.add(num1);
                        }
                    }
                    if (tempArr1.isEmpty()) {
                        return false;
                    }
                    ERZ_MAP[i][y] = tempArr1;
                    if (tempArr1.size() == 1) {
                        calcOne(i, y);
                    }
                }
            }
//                    宫内计算
            for (short i = (short) (x / 3 * 3), i0 = 0; i0 < 3; i++, i0++) {
                for (short j = (short) (y / 3 * 3), j0 = 0; j0 < 3; j++, j0++) {
                    final List<Short> tempArr0 = ERZ_MAP[i][j];
                    if (tempArr0.size() > 1) {
                        final List<Short> tempArr1 = new ArrayList<>();
                        Iterator<Short> it = tempArr0.iterator();
                        while (it.hasNext()) {
                            final short num1 = it.next();
                            if (num1 != num) {
                                tempArr1.add(num1);
                            }
                        }
                        if (tempArr1.isEmpty()) {
                            return false;
                        }
                        ERZ_MAP[i][j] = tempArr1;
                        if (tempArr1.size() == 1) {
                            calcOne(i, j);
                        }
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        long t0 = System.currentTimeMillis();
        final Sd sd = new Sd();
        sd.initMap();
        sd.calc();
        long t1 = System.currentTimeMillis();
        System.out.println("打印二进制结果数组");
        sd.printEjzMap();
        System.out.println("耗时： " + (t1 - t0));
    }

}